package month1;

public class PathSumIII437_05 {
    public static void main(String[] args) {
        System.out.println(pathSum(new TreeNode(new Integer[]{1000000000, 1000000000, null, 294967296, null, 1000000000, null, 1000000000, null, 1000000000}), 0));
    }

    static int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        return dfs(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    static int dfs(TreeNode root, long target) {
        if (root == null) {
            return 0;
        }
        return (root.val == target ? 1 : 0) + dfs(root.left, target - root.val) + dfs(root.right, target - root.val);
    }
}
